<?php
/**
 * @title 29.两数相除 - 二分移位
 * @author start2004
 */

class Solution {

    /**
     * @param Integer $dividend
     * @param Integer $divisor
     * @return Integer
     */
    function divide($dividend, $divisor) {
        /**
         * @since 2020-07-13 32位有符号整数最大值, 最小值
         * +2147483647
         * -2147483648
         */
        $max = pow(2, 31)-1;
        $min = -1-$max;
        
        /**
         * @since 2020-07-03 -2^31/-1 = 2^31, 溢出处理
         */
        if($dividend == $min AND $divisor == -1){
            return $max;
        } else {}

        /**
         * @since 2020-07-03 处理分母最大负数, 这样分母可以取正
         */
        if($divisor == $min){
            if($dividend == $min){
                return 1;
            } else {
                return 0;
            }
        } else {}

        /**
         * @since 2020-07-13 商-结果
         */
        $result = 0;

        /**
         * @since 2020-07-13 结果正负, 分母,分子取正
         */
        $symbol = false;
        if($divisor < 0){
            $divisor = abs($divisor);
            $symbol = !$symbol;
        }
        if($dividend < 0){
            $symbol = !$symbol;

            /**
             * @since 2020-07-13 分子直接取正, 可能导致溢出
             */
            if($dividend == $min){
                /**
                 * @since 2020-07-13 分母不为0, 加上一个正数分母, 再取正
                 */
                $dividend = abs($dividend+$divisor);
                $result = 1;
            } else {
                $dividend = abs($dividend);
            }
        } else {}
        // return [$dividend, $divisor, $result];

        /**
         * @since 2020-07-13 取正后, 分子小于分母
         */
        if($dividend<$divisor){
            if($result == 1 AND $symbol){
                return -1;
            } else {
                return $result;
            }
        } else {}

        /**
         * @since 2020-07-13 分母可移位上限right, 下限left
         */
        $bin = decbin($divisor);
        $right = 31-strlen($bin);
        $left = 0;
        // return [$left, $right];

        /**
         * @since 2020-07-13 二分移位
         */
        $i=1;
        do{
            while($right-$left > 1){
                $mid = ($left+$right)>>1;
                $val = $divisor<<$mid;
                // echo "left={$left}, right={$right}, mid={$mid}, val={$val}", PHP_EOL;

                if($val>$dividend){
                    $right = $mid;
                } else {
                    $left = $mid;
                }
            }

            /**
             * @since 2020-07-13 倍数
             */
            $result += 1<<$left;
            $dividend -= $divisor<<$left;
            // echo "left={$left}, a={$dividend}, c={$result}", str_repeat(PHP_EOL, 3);

            /**
             * @since 2020-07-13 next while
             */
            $left = 0;
        }while($dividend >= $divisor);

        /**
         * @since 2020-07-13 正负符号
         */
        if($symbol){
            $result = 0-$result;
        } else {}

        /**
         * @return
         */
        return $result;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.03_2.php
 */
$datas = [
    [-1006986286,-2145851451],
    // [10, 3],
    // [-2147483648, -1],
    // [2147483647, 1],
    // [-2147483648, -2147483648],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->divide($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
